package leetcode.hot100;

public class Solution31 {
    public static void main(String[] args) {
        Solution31 s = new Solution31();
        int[] nums = new int[]{1,2,3,4};
        s.nextPermutation(nums);
    }

    public void nextPermutation(int[] nums) {
        //需要找到一个比原数组大的下限
        //先确定数组中存在可交换的数对，使数组增大
        int idx = nums.length - 2;
        while(idx>=0 && nums[idx]>=nums[idx+1]) idx--;
        //如果idx=-1说明数组已经最大了
        if(idx==-1){
            reverse(nums,0,nums.length-1);
            return;
        }
        //再从后向前找第一个比num[idx]大的数
        int target = nums.length - 1;
        while(nums[target]<=nums[idx]) target--;
        //交换target和idx
        swap(nums,idx,target);
        //使idx之后的元素升序，即反转这些元素
        reverse(nums,idx+1,nums.length-1);
    }

    public void reverse(int[] nums, int start, int end){
        for(int i=start;i<=end;i++){
            swap(nums,i,start+end-i);
        }
    }
    public void swap(int[] nums, int i, int j){
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}
